#include <unordered_set>
using namespace std;

struct ListNode {
  int val;
  ListNode *next;
  ListNode(int x) : val(x), next(nullptr) {}
};

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
  unordered_set<ListNode *> nodeSet;
  while (headA != nullptr) {
    nodeSet.insert(headA);
    headA = headA->next;
  }
  while (headB != nullptr) {
    if (nodeSet.count(headB)) {
      return headB;
    }
    nodeSet.insert(headB);
    headB = headB->next;
  }
  return nullptr;
}
// 双指针解法
ListNode *getIntersectionNode_(ListNode *headA, ListNode *headB) {
  if (headA == nullptr || headB == nullptr) {
    return nullptr;
  }
  // 初始化两个指针
  ListNode *tempA = headA, *tempB = headB;
  while (tempA != tempB) {
    tempA = tempA != nullptr ? tempA->next : headB;
    tempB = tempB != nullptr ? tempB->next : headA;
  }
  return tempA;
}